{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Well-Performing Interval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #hash-table #prefix-sum #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #哈希表 #前缀和 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestWPI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #表现良好的最长时间段"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一份工作时间表&nbsp;<code>hours</code>，上面记录着某一位员工每天的工作小时数。</p>\n",
    "\n",
    "<p>我们认为当员工一天中的工作小时数大于&nbsp;<code>8</code> 小时的时候，那么这一天就是「<strong>劳累的一天</strong>」。</p>\n",
    "\n",
    "<p>所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格<strong> 大于</strong>「不劳累的天数」。</p>\n",
    "\n",
    "<p>请你返回「表现良好时间段」的最大长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hours = [9,9,6,0,6,6,9]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长的表现良好时间段是 [9,9,6]。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>hours = [6,6,6]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= hours.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= hours[i] &lt;= 16</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-well-performing-interval](https://leetcode.cn/problems/longest-well-performing-interval/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-well-performing-interval](https://leetcode.cn/problems/longest-well-performing-interval/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,9,6,0,6,6,9]', '[6,6,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pos = {}\n",
    "        ans = s = 0\n",
    "        for i in range(n):\n",
    "            s += 1 if hours[i] > 8 else -1\n",
    "            if s > 0:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                if s-1 in pos:\n",
    "                    ans = max(ans, i - pos[s - 1])\n",
    "                if s not in pos:\n",
    "                    pos[s] = i\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pos = [0] * (len(hours) + 2)  # 记录前缀和首次出现的位置\n",
    "        ans = s = 0\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s -= 1 if h > 8 else -1  # 取反，改为减法\n",
    "            if s < 0:\n",
    "                ans = i\n",
    "            else:\n",
    "                if pos[s + 1]:  # 原本是 s-1，取反改为 s+1\n",
    "                    ans = max(ans, i - pos[s + 1])  # 这里手写 if 会更快\n",
    "                if pos[s] == 0:\n",
    "                    pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def geneCumList(self,l):\n",
    "        cur_sum,Sum = 0,[]\n",
    "        for v in l:\n",
    "            cur_sum += v\n",
    "            Sum.append(cur_sum)\n",
    "        return Sum\n",
    "\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        hours = [1 if h>8 else -1 for h in hours]\n",
    "        if not 1 in hours:\n",
    "            return 0\n",
    "        # initial\n",
    "        n = len(hours)\n",
    "        # 生成两个单调stack\n",
    "        Sum = self.geneCumList(hours)\n",
    "        front_s = [(0,-1)]\n",
    "        for i in range(n):\n",
    "            if Sum[i]<front_s[-1][0]:\n",
    "                front_s.append((Sum[i],i))\n",
    "        later_s = [(Sum[-1],n-1)]\n",
    "        for j in range(n-2,-1,-1):\n",
    "            if Sum[j]>later_s[-1][0]:\n",
    "                later_s.append((Sum[j],j))\n",
    "        later_s = later_s[::-1]\n",
    "        # 扫描答案\n",
    "        res = 1 # 必定至少有一个1\n",
    "        while len(front_s) and len(later_s) and later_s[0][0]>front_s[-1][0]:\n",
    "            if later_s[-1][0]<=front_s[-1][0]:\n",
    "                later_s.pop()\n",
    "                continue\n",
    "            if later_s[-1][-1]<=front_s[-1][-1]:\n",
    "                later_s.pop()\n",
    "                front_s.pop()\n",
    "                continue\n",
    "                \n",
    "            vj,j = later_s.pop()\n",
    "            # 二分\n",
    "            while len(front_s) and vj>front_s[-1][0]:\n",
    "                tmp = front_s.pop()\n",
    "                if len(front_s)==0 or vj<=front_s[-1][0]:\n",
    "                    res = max(res,j-tmp[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        pos = {}\n",
    "        for i, x in enumerate(hours):\n",
    "            s += 1 if x > 8 else -1\n",
    "            if s > 0:\n",
    "                ans = i + 1\n",
    "            elif s - 1 in pos:\n",
    "                ans = max(ans, i - pos[s - 1])\n",
    "            if s not in pos:\n",
    "                pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 单调栈\n",
    "    # https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/\n",
    "    def longestWPI1(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)  # 前缀和\n",
    "        st = [0]  # s[0]\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            s[j] = s[j - 1] + (1 if h > 8 else -1)\n",
    "            if s[j] < s[st[-1]]:\n",
    "                st.append(j)  # 感兴趣的 j\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())  # [st[-1],i) 可能是最长子数组\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # # 利用前缀和的连续性\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pos = [0] * (len(hours) + 2)  # 记录前缀和首次出现的位置\n",
    "        ans = s = 0\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s += 1 if h > 8 else -1  # 取反，改为减法\n",
    "            if s > 0:\n",
    "                ans = i\n",
    "            else:\n",
    "                if pos[s - 1]:\n",
    "                    ans = max(ans, i - pos[s - 1])  # 这里手写 if 会更快\n",
    "\n",
    "                if pos[s] == 0:\n",
    "                    pos[s] = i\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pos = [0] * (n + 2)\n",
    "        ans = prefix = 0\n",
    "        for i in range(n):\n",
    "            prefix -= 1 if hours[i] > 8 else -1\n",
    "            if prefix < 0:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                if pos[prefix + 1]:\n",
    "                    ans = max(ans, i - pos[prefix + 1] + 1)\n",
    "                if pos[prefix] == 0:\n",
    "                    pos[prefix] = i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        list_1 = []\n",
    "        for h in hours:\n",
    "            if h > 8:\n",
    "                list_1.append(1)\n",
    "            else:\n",
    "                list_1.append(-1)\n",
    "\n",
    "        list_2 = []\n",
    "        s = 0\n",
    "        for i in list_1:\n",
    "            s += i \n",
    "            list_2.append(s)\n",
    "\n",
    "        hash_map = {0: [-1]}\n",
    "        for idx, val in enumerate(list_2):\n",
    "            if val in hash_map:\n",
    "                hash_map[val] = hash_map[val] + [idx]\n",
    "            else:\n",
    "                hash_map[val] = [idx]\n",
    "        \n",
    "        max_len = 0\n",
    "        for i in range(len(hours)):\n",
    "            if list_2[i] > 0:\n",
    "                max_len = max(max_len, i + 1)\n",
    "            else:\n",
    "                temp = list_2[i] - 1\n",
    "                if temp in hash_map:\n",
    "                    left = hash_map[temp][0]\n",
    "                    max_len = max(max_len, i - left)\n",
    "        \n",
    "        return max_len\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def longestWPI(self, hours: List[int]) -> int:\n",
    "#         res,s,c=0,0,{}\n",
    "#         for i,h in enumerate(hours):\n",
    "#             s+=1 if h>8 else -1\n",
    "#             if s>0:res=i+1\n",
    "#             elif s-1 in c:res=max(res,i-c[s-1])\n",
    "#             if s not in c:c[s]=i \n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pos = [0] * (n + 2)\n",
    "\n",
    "        ans = s = 0\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s -= 1 if h > 8 else -1\n",
    "            if s < 0:\n",
    "                ans = i\n",
    "            else:\n",
    "                # \n",
    "                # 如果存在比s小1的数字\n",
    "                if pos[s + 1]:\n",
    "                    ans = max(ans, i - pos[s+1])\n",
    "                # 如果这个位置没有访问过，就记下来\n",
    "                if pos[s] == 0:\n",
    "                    pos[s] = i\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pos = [0]*(len(hours)+2)\n",
    "        ans = s = 0\n",
    "        for i,h in enumerate(hours,1):\n",
    "            s -=1 if h>8 else -1\n",
    "            if s<0:\n",
    "                ans = i\n",
    "            else:\n",
    "                if pos[s+1]:\n",
    "                    ans = max(ans,i-pos[s+1])\n",
    "                if pos[s]==0:\n",
    "                    pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        new_list = []\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i] > 8:\n",
    "                new_list.append(1)\n",
    "            else:\n",
    "                new_list.append(-1)\n",
    "        \n",
    "        dic_sums = collections.defaultdict()\n",
    "        dic_sums[0] = 0\n",
    "\n",
    "        # 前缀和\n",
    "        for i in range(len(new_list)):\n",
    "            dic_sums[i+1] = dic_sums[i] + new_list[i]\n",
    "        print(dict(dic_sums))\n",
    "\n",
    "        ans = 0\n",
    "        stack = []\n",
    "\n",
    "        for i in range(len(hours)+1):\n",
    "            if not stack or dic_sums[stack[-1]] > dic_sums[i]:\n",
    "                stack.append(i)\n",
    "        print(stack)\n",
    "        i = len(hours)\n",
    "\n",
    "        while i > ans:\n",
    "            while stack and dic_sums[stack[-1]] < dic_sums[i]:\n",
    "                ans = max(ans, i- stack[-1])\n",
    "                stack.pop()\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        res=s=0\n",
    "        pos={}\n",
    "        for i in range(len(hours)):\n",
    "            s+=1 if hours[i]>8 else -1\n",
    "            if s>0:\n",
    "                res=max(res,i+1)\n",
    "            elif s-1 in pos:\n",
    "                res=max(res,i-pos[s-1])\n",
    "            if s not in pos:\n",
    "                pos[s]=i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pos = [0] * (len(hours) + 2)  # 记录前缀和首次出现的位置\n",
    "        ans = s = 0\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s -= 1 if h > 8 else -1  # 取反，改为减法\n",
    "            if s < 0:\n",
    "                ans = i\n",
    "            else:\n",
    "                if pos[s + 1]:  # 原本是 s-1，取反改为 s+1\n",
    "                    ans = max(ans, i - pos[s + 1])  # 这里手写 if 会更快\n",
    "                if pos[s] == 0:\n",
    "                    pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        for i in range(n):\n",
    "            if hours[i]>8:\n",
    "                hours[i]=1\n",
    "            else:\n",
    "                hours[i]=-1\n",
    "        ans = 0\n",
    "        su = 0\n",
    "        map = dict()\n",
    "        map[0] = -1\n",
    "        for i in range(n):\n",
    "            su += hours[i]\n",
    "            if su>0:\n",
    "                ans = max(ans,i+1)\n",
    "            else:\n",
    "                if su-1 in map:\n",
    "                    ans = max(ans,i-map[su-1])\n",
    "            if su not in map:\n",
    "                map[su]=i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pos={}\n",
    "        ans=0\n",
    "        s=0\n",
    "        for i,x in enumerate(hours):\n",
    "            if x>8:\n",
    "                s+=1\n",
    "            else:\n",
    "                s-=1\n",
    "            if s>0:\n",
    "                ans=i+1\n",
    "            elif s-1 in pos:\n",
    "                ans = max(ans,i-pos[s-1])\n",
    "            if s not in pos:\n",
    "                pos[s]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        #st=[0]\n",
    "        n=len(hours)\n",
    "        #s=[0]*(n+1)\n",
    "        ##[0,1,2,1,0,-1,-2,-1]\n",
    "        ##[0,-1,-2,-3]\n",
    "        #[0,-1,-2,-1,0]\n",
    "        #[0,0,9,9]\n",
    "        #s[j]=s[i]-1\n",
    "        #for i,h in enumerate(hours,1):\n",
    "        #    s[i]=s[i-1]+(1 if h>8 else -1)\n",
    "        #    if s[i]<s[st[-1]]: st.append(i)\n",
    "        #ans=0\n",
    "        #for i in range(n,0,-1):\n",
    "        #    while st and s[i]>s[st[-1]]:\n",
    "        #        ans=max(ans,i-st.pop())\n",
    "        #return ans\n",
    "\n",
    "        pos=[0]*(n+2)\n",
    "        ans=s=0\n",
    "        for i,x in enumerate(hours,1):\n",
    "            s += (1 if x<=8 else -1)\n",
    "            if s<0:\n",
    "                ans=i\n",
    "            else:\n",
    "                if pos[s+1]:\n",
    "                    ans=max(ans,i-pos[s+1])\n",
    "                if pos[s]==0:\n",
    "                    pos[s]=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0]*(n + 1)\n",
    "        st = [0]\n",
    "        for i,x in enumerate(hours,1):\n",
    "            s[i] = s[i - 1] + (1 if x > 8 else -1)\n",
    "            if s[st[-1]] > s[i]:\n",
    "                st.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n,0,-1):\n",
    "            while st and s[st[-1]] < s[i]:\n",
    "                ans = max(ans,i - st.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self,hours:list[int])->int:\n",
    "\n",
    "        prefix_sum_map={}\n",
    "        prefix_sum_map[0]=-1\n",
    "        ans =0\n",
    "        sum_val=0\n",
    "\n",
    "        for i in range(len(hours)):\n",
    "            sum_val+=1 if hours[i]>8 else-1\n",
    "\n",
    "            if sum_val>0:\n",
    "                ans=i+1\n",
    "            else:\n",
    "                if sum_val-1 in prefix_sum_map:\n",
    "                    ans = max(ans,i-prefix_sum_map[sum_val-1])\n",
    "\n",
    "            if sum_val not in prefix_sum_map:\n",
    "                prefix_sum_map[sum_val]=i\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * ( n + 1 )\n",
    "        st = [0]\n",
    "        for j,h in enumerate(hours,1):\n",
    "            s[j] = s[j-1] + (1 if h > 8 else -1)\n",
    "            if s[j] < s[st[-1]]: st.append(j)\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        res=s=0\n",
    "        pos={0:-1}\n",
    "        for i in range(len(hours)):\n",
    "            s+=1 if hours[i]>8 else -1\n",
    "            if s>0: res=max(res,i+1)\n",
    "            if s-1 in pos:\n",
    "                res=max(res,i-pos[s-1])\n",
    "            if s not in pos:\n",
    "                pos[s]=i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        maxinterval = 0\n",
    "        presum = 0\n",
    "        map = {}\n",
    "        for i in range(len(hours)):\n",
    "            presum += 1 if hours[i] > 8 else -1\n",
    "            if presum > 0:\n",
    "                maxinterval = i + 1\n",
    "            else:\n",
    "                print(presum, i)\n",
    "                if map.get(presum) == None:\n",
    "                    map[presum] = i\n",
    "                \n",
    "                if map.get(presum - 1) != None:\n",
    "                    j = map[presum - 1]\n",
    "                    interval = i - j\n",
    "                    maxinterval = max(maxinterval, interval)\n",
    "        return maxinterval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        score = ans = 0\n",
    "        pool = {}\n",
    "        for i, h in enumerate(hours):\n",
    "            score += 1 if h > 8 else -1\n",
    "            if score > 0:\n",
    "                ans = i + 1\n",
    "            pool.setdefault(score, i)\n",
    "            if score - 1 in pool:\n",
    "                ans = max(ans, i - pool[score - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxsl(self, numbers):\n",
    "        # print(numbers)\n",
    "        res = dict()\n",
    "        res[0] = -1\n",
    "        ans = 0\n",
    "        pre_sum = 0\n",
    "        min_sum = 0\n",
    "        for index in range(len(numbers)):\n",
    "            pre_sum += 1 if numbers[index] > 8 else -1\n",
    "            # print(index, pre_sum)\n",
    "            if pre_sum not in res:\n",
    "                res[pre_sum] = index\n",
    "            if pre_sum > 0:\n",
    "                ans = max(ans, index+1)\n",
    "            else:\n",
    "                # print(index, min_sum, pre_sum)\n",
    "                if min_sum > pre_sum:\n",
    "                    min_sum = pre_sum\n",
    "                else:\n",
    "                    for d in range(pre_sum - 1, min_sum - 1, -1):\n",
    "                    # print(index, d)\n",
    "                        if d in res:\n",
    "                            ans = max(ans, index - res[d])\n",
    "                            break\n",
    "        return ans\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        # for i in range(len(hours)):\n",
    "            # hours[i] = 1 if hours[i] > 8 else -1\n",
    "        return self.maxsl(hours)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        hash_table = {0:-1}\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i]>8:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur -= 1\n",
    "            if cur>0:\n",
    "                ans = max(ans, i+1)\n",
    "            if cur<=0:\n",
    "                # print(cur, cur-1)\n",
    "                if cur-1 in hash_table:\n",
    "                    ans = max(ans, i-hash_table[cur-1])\n",
    "            if cur not in hash_table:\n",
    "                hash_table[cur] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        maxinterval = 0\n",
    "        presum_dict = dict()\n",
    "        presum = 0\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i] > 8:\n",
    "                presum += 1\n",
    "            else:\n",
    "                presum += -1\n",
    "                # 计算前缀和\n",
    "            if presum > 0 : # presum>0 意味着hours在索引[0,i]内表现良好\n",
    "                maxinterval = i + 1 # [0,i]之间有i+1个元素\n",
    "                # presum大于0的时候，表现良好时间段的最大长度最有可能就是从0到i的数组\n",
    "            else:\n",
    "                if presum not in presum_dict: # 新的负数presum要记入哈希表\n",
    "                    presum_dict[presum] = i # [0,i]\n",
    "                    # presum在小于0时，presum越小，索引越靠后\n",
    "                if presum - 1 in presum_dict: \n",
    "                    # 如果presum-1在presum_dict，就意味着遇到presum不是第一次了\n",
    "                    j = presum_dict[presum - 1] \n",
    "                    # [0,j]的前缀和presum-1，与当前索引i（索引i第k次，k大于1，让前缀和[0,i]等于presum）\n",
    "                    # 那么这个表现良好的时间段数组为hours[j+1,i],长度为i-（j+1）+1=i-j\n",
    "                    interval = i - j \n",
    "                    maxinterval = max(maxinterval,interval)\n",
    "        return maxinterval\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        d = {0: -1}\n",
    "        res = pre_sum = 0\n",
    "        for i, h in enumerate(hours):\n",
    "            if h > 8:\n",
    "                pre_sum += 1\n",
    "            else:\n",
    "                pre_sum -= 1\n",
    "            if pre_sum > 0:\n",
    "                res = max(res, i+1)\n",
    "            if pre_sum-1 in d: \n",
    "                res = max(res, i - d[pre_sum-1])\n",
    "            if pre_sum not in d: \n",
    "                d[pre_sum] = i # 有用的只记录\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        stack = [0]\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            if hours[i-1] > 8:\n",
    "                prefix[i] = prefix[i-1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i-1] - 1\n",
    "            if prefix[stack[-1]] > prefix[i]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for end in range(n, 0, -1):\n",
    "            while stack and prefix[stack[-1]] < prefix[end]:\n",
    "                res = max(res, end-stack[-1])\n",
    "                stack.pop()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        st = [0]\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + (1 if hours[i] > 8 else -1)\n",
    "            if s[i + 1] < s[st[-1]]:\n",
    "                st.append(i + 1)\n",
    "        # print(st)\n",
    "        ans = 0\n",
    "        for i in range(n, -1, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pos = dict()\n",
    "        ans = 0\n",
    "        s = 0\n",
    "\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s += 1 if h > 8 else -1\n",
    "            if s > 0:\n",
    "                ans = i\n",
    "            else:\n",
    "                # 如果是负数，且出现过s-1这个数字\n",
    "                # 区间就是[pos[s-1]+1, i这一段]\n",
    "                if s - 1 in pos:\n",
    "                    ans = max(ans, i - pos[s-1])\n",
    "                if not s in pos:\n",
    "                    pos[s] = i\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        # 【劳累的天数】 - 【不劳累的天数】 >= 1\n",
    "        # 本质上是在计算这个问题\n",
    "        # 转换成 前缀和问题，[0~r] - [0~l]的数值 >=1，即可\n",
    "        map1 = {0: -1}\n",
    "        ans = s = 0\n",
    "        for i, x in enumerate(hours):\n",
    "            s += 1 if x > 8 else -1\n",
    "            y = s - 1 # aim = 1，需要计算的是 >=1的子数组的累加和\n",
    "            if s > 0: # 累加和>0的时候，就是 【0~i】位置满足题意\n",
    "                ans = i + 1\n",
    "            if y in map1: # 如果 s <0的时候，才去  减去 【0~？】的累加和\n",
    "                ans = max(ans, i - map1[y])\n",
    "            if s not in map1:\n",
    "                map1[s] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)  # 前缀和\n",
    "        st = [0]  # s[0]\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            s[j] = s[j - 1] + (1 if h > 8 else -1)\n",
    "            if s[j] < s[st[-1]]: st.append(j)  # 感兴趣的 j\n",
    "        res = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                res = max(res, i - st.pop())  # [st[-1],i) 可能是最长子数组\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pre_sum = [0] *(len(hours)+1)\n",
    "        stack = [0]\n",
    "\n",
    "        for i in range(1,len(hours)+1):\n",
    "            if hours[i-1] > 8:\n",
    "                pre_sum[i] = pre_sum[i-1]+1\n",
    "            else:\n",
    "                pre_sum[i] = pre_sum[i-1]-1\n",
    "            if pre_sum[stack[-1]] > pre_sum[i]:\n",
    "                stack.append(i)\n",
    "        res = 0\n",
    "        for i in range(len(hours),0,-1):\n",
    "            while stack and pre_sum[i]-pre_sum[stack[-1]]>0:\n",
    "                res = max(res,i-stack[-1])\n",
    "                stack.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        # 某个前缀和，最早出现的位置\n",
    "        prefix_sum_map = {}\n",
    "        # 0这个前缀和，最早出现在-1，一个数也没有的时候\n",
    "        prefix_sum_map[0] = -1\n",
    "        ans = 0\n",
    "        sum_val = 0\n",
    "\n",
    "        for i in range(len(hours)):\n",
    "            # 更新前缀和，大于8小时为1，小于等于8小时为-1\n",
    "            sum_val += 1 if hours[i] > 8 else -1\n",
    "\n",
    "            if sum_val > 0:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                # sum <= 0\n",
    "                if sum_val - 1 in prefix_sum_map:\n",
    "                    ans = max(ans, i - prefix_sum_map[sum_val - 1])\n",
    "\n",
    "            if sum_val not in prefix_sum_map:\n",
    "                prefix_sum_map[sum_val] = i\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        # 记录表现好的时间段起初位置\n",
    "        accSum = 0\n",
    "        dicts = {}\n",
    "        maxIndex = 0\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i]>8:\n",
    "                accSum += 1\n",
    "            else:\n",
    "                accSum -= 1\n",
    "            if accSum > 0:\n",
    "                maxIndex = i+1\n",
    "            else:\n",
    "                if accSum - 1 in dicts:\n",
    "                    maxIndex = max(maxIndex, i - dicts[accSum-1])\n",
    "                if accSum not in dicts:\n",
    "                    dicts[accSum] = i\n",
    "        return maxIndex\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        dic =dict()\n",
    "        ans = 0\n",
    "        s = 0 #前缀和\n",
    "        for i,h in enumerate(hours):\n",
    "            if h>8:\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "\n",
    "            if s>0:\n",
    "                ans = max(ans,i+1)\n",
    "                # continue\n",
    "            # s-k = 1==>k = s-1\n",
    "            if (s-1) in dic:\n",
    "                ans = max(ans, i-dic[s-1])\n",
    "            if s not in dic:\n",
    "                dic[s] = i\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        st = [0]\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + (1 if hours[i]>8 else -1)\n",
    "            if s[i+1] < s[st[-1]]: st.append(i+1)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pre = list(accumulate(list((x > 8) for x in hours), initial=0))\n",
    "        ret = 0\n",
    "        for i in range(len(hours)):\n",
    "            for j in range(i, len(hours)):\n",
    "                tmp = pre[j+1] - pre[i]\n",
    "                if tmp > (j - i + 1) // 2:\n",
    "                    ret = max(ret, j - i + 1)\n",
    "        return ret \n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ret = s = 0\n",
    "        d = {}\n",
    "        for i, x in enumerate(hours):\n",
    "            s += 1 if x > 8 else -1\n",
    "            if s > 0:\n",
    "                ret = i + 1\n",
    "            elif s - 1 in d:\n",
    "                ret = max(ret, i - d[s-1])\n",
    "            if s not in d:\n",
    "                d[s] = i\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:        \n",
    "        mp = {0: -1}\n",
    "        ans = 0 \n",
    "        add = 0\n",
    "        for i in range(len(hours)):\n",
    "            add += 1 if hours[i] > 8 else -1\n",
    "            if add > 0:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                if add - 1 in mp.keys():  # 找 add-1 因为从 0 开始而且数组连续，如果没有 add-1，就没有 add-2 这些，所以找 add-1 即可\n",
    "                    ans = max(ans, i - mp[add - 1]) \n",
    "                if add not in mp.keys():\n",
    "                    mp[add] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        pos = {}\n",
    "        for i, x in enumerate(hours):\n",
    "            s += 1 if x > 8 else -1\n",
    "            if s > 0:\n",
    "                ans = i + 1\n",
    "            elif s - 1 in pos:\n",
    "                ans = max(ans, i - pos[s - 1])\n",
    "            if s not in pos:\n",
    "                pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0]*(n+1)\n",
    "        st = [0]\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            s[i] = s[i - 1] + 2*(h > 8) - 1\n",
    "            if s[st[-1]] > s[i]:\n",
    "                st.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        res = 0\n",
    "        hash_map = {0:-1}\n",
    "        prix = 0\n",
    "        for i in range(len(hours)):\n",
    "            prix += 1 if hours[i] > 8 else - 1\n",
    "            if prix > 0:\n",
    "                res = max(res, i + 1)\n",
    "            else:\n",
    "                if prix - 1 in hash_map:\n",
    "                    res = max(res, i - hash_map[prix - 1])\n",
    "                if prix not in hash_map:\n",
    "                    hash_map[prix] = i\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)  # 前缀和\n",
    "        st = [0]  # s[0]\n",
    "        hours = [1 if h > 8 else -1 for h in hours]\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + hours[i]\n",
    "        for j in range(n):\n",
    "            if s[j] < s[st[-1]]: st.append(j)  # 感兴趣的 j\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())  # [st[-1],i) 可能是最长子数组\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: list[int]) -> int:\n",
    "        l = len(hours)\n",
    "        b = []\n",
    "        ans = 0\n",
    "        high = 0\n",
    "        last = 0\n",
    "        for i in range(l):\n",
    "            if hours[i] > 8: high += 1\n",
    "            else: high += -1\n",
    "            hours[i] = high\n",
    "            if high < last:\n",
    "                last += -1\n",
    "                b.append(i)\n",
    "            low = -len(b)\n",
    "            if hours[i] > 0:\n",
    "                ans = max(ans, i+1)\n",
    "            elif hours[i] > low:\n",
    "                ans = max(ans, i - b[-hours[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        prefix_sum_map={}\n",
    "        prefix_sum_map[0]=-1\n",
    "        ans=0\n",
    "        sum_val=0\n",
    "        \n",
    "        for i in range(len(hours)):\n",
    "            sum_val +=1 if hours[i]>8 else -1\n",
    "            \n",
    "            if sum_val>0:\n",
    "                ans=i+1\n",
    "                \n",
    "            else:\n",
    "                if sum_val -1 in prefix_sum_map:\n",
    "                    ans=max(ans,i-prefix_sum_map[sum_val-1])\n",
    "            \n",
    "            if sum_val not in prefix_sum_map:\n",
    "                prefix_sum_map[sum_val]=i\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        info = [0]\n",
    "        st = [0]\n",
    "        for idx, hour in enumerate(hours):\n",
    "            if hour > 8:\n",
    "                info.append(info[-1]+1)\n",
    "            else:\n",
    "                info.append(info[-1]-1)\n",
    "            if info[-1] < info[st[-1]]:\n",
    "                st.append(idx+1)\n",
    "        ans = 0\n",
    "        for j in range(len(info)-1, 0, -1):\n",
    "            while st and info[j] > info[st[-1]]:\n",
    "                i = st.pop()\n",
    "                ans = max(ans, j-i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ans=s=0\n",
    "        pos={}\n",
    "        for i,x in enumerate(hours):\n",
    "            s += 1 if x>8 else -1\n",
    "            if s>0:\n",
    "                ans = i+1\n",
    "            elif s-1 in pos:\n",
    "                ans = max(ans, i-pos[s-1])\n",
    "            if s not in pos:\n",
    "                pos[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        hash_table = {0:-1}\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i]>8:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur -= 1\n",
    "            if cur>0:\n",
    "                ans = max(ans, i+1)\n",
    "            else:\n",
    "                # print(cur, cur-1)\n",
    "                if cur-1 in hash_table:\n",
    "                    ans = max(ans, i-hash_table[cur-1])\n",
    "            if cur not in hash_table:\n",
    "                hash_table[cur] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)\n",
    "        st = [0]\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            if h > 8:\n",
    "                s[i] = s[i-1] + 1\n",
    "            else:\n",
    "                s[i] = s[i-1] - 1\n",
    "            # 需要维护前缀和递减的索引\n",
    "            if s[i] < s[st[-1]]:\n",
    "                st.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st[-1])\n",
    "                st.pop()\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        acc = [0]\n",
    "        for h in hours: acc.append(acc[-1] + (1 if h > 8 else -1))\n",
    "        st = []\n",
    "        for i,x in enumerate(acc):\n",
    "            if not st or acc[st[-1]] > x: st.append(i)\n",
    "        ans = 0\n",
    "        n = len(acc)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and acc[i] > acc[st[-1]]:\n",
    "                ans = max(ans,i-st.pop())\n",
    "            if not st: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        suml = [0] * n\n",
    "        for i,hour in enumerate(hours):\n",
    "            suml[i] = 1 if hour>8 else -1\n",
    "            if i > 0 :\n",
    "                suml[i] = 1 if hour>8 else -1\n",
    "                suml[i] += suml[i-1]\n",
    "        res = 0\n",
    "        d = {}\n",
    "        for i,sumc in enumerate(suml):\n",
    "            if sumc > 0:\n",
    "                res = max(res,i+1)\n",
    "            else:\n",
    "                if sumc-1 in d:\n",
    "                    res = max(res,i-d[sumc-1])\n",
    "                if sumc not in d:\n",
    "                    d[sumc]=i\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        prefixSum = [0] * (n+1)\n",
    "        decStack = []   # monotonic decreasing stack, element: index of prefix sum\n",
    "        \n",
    "        # 1. O(N) calculate prefix sum and build the monotonic stack\n",
    "        for i in range(n+1):\n",
    "            if i >= 1:\n",
    "                prefixSum[i] = prefixSum[i-1] + (1 if hours[i-1] > 8 else -1)    # convert hour to +1 (h>8), -1 (h<=8)\n",
    "            if not decStack or prefixSum[decStack[-1]] > prefixSum[i]:\n",
    "                decStack.append(i)\n",
    "        \n",
    "        # 2. O(N) iterates over prefix sum \n",
    "        ans = 0\n",
    "        for i in range(n, -1, -1):   # iterates over prefix sum backward\n",
    "            # iterates over monotonic stack backward\n",
    "            while decStack and prefixSum[decStack[-1]] < prefixSum[i]:\n",
    "                ans = max(ans, i - decStack.pop())     # well-performing interval [prefixSum[decStack[-1]], i)\n",
    "                \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "\n",
    "        prefix = [0] * (n + 1)\n",
    "        stack = [0] # prefix[0]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            prefix[i] =  prefix[i - 1] + (1 if hours[i - 1] > 8 else -1)\n",
    "            if prefix[i] < prefix[stack[-1]]:\n",
    "                stack.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while stack and prefix[i] > prefix[stack[-1]]:\n",
    "                res = max(res, i - stack.pop())\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        s = []\n",
    "        t = 0\n",
    "        for h in hours:\n",
    "            if h > 8:\n",
    "                t += 1\n",
    "            else:\n",
    "                t -= 1\n",
    "            s.append(t)\n",
    "        # 对于每个值找到 < 该值最左侧的值\n",
    "        m = {}\n",
    "        res = 0\n",
    "        for i, si in enumerate(s):\n",
    "            if si > 0:\n",
    "                res = max(res, i + 1)\n",
    "            if si not in m:\n",
    "                m[si] = i\n",
    "            if si - 1 in m:\n",
    "                res = max(res, i - m[si-1])\n",
    "                m[si] = min(m[si-1], m[si])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)  # 前缀和\n",
    "        st = [0]  # s[0]\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            s[j] = s[j - 1] + (1 if h > 8 else -1)\n",
    "            if s[j] < s[st[-1]]:\n",
    "                st.append(j)  # 感兴趣的 j\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())  # [st[-1],i) 可能是最长子数组\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ls = [[0, -1]]\n",
    "        count = 0\n",
    "        ret = 0\n",
    "        for index, val in enumerate(hours):\n",
    "            if val > 8:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count < -ls[-1][0]:\n",
    "                ls.append([-count, index])\n",
    "            else:\n",
    "                i = bisect_right(ls, -count, key=lambda x: x[0])\n",
    "                if i < len(ls):\n",
    "                    ret = max(ret, index - ls[i][1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        pre = list(accumulate(list((x > 8) for x in hours), initial=0))\n",
    "        ret = 0\n",
    "        for i in range(len(hours)):\n",
    "            for j in range(i, len(hours)):\n",
    "                tmp = pre[j+1] - pre[i]\n",
    "                if tmp > (j - i + 1) // 2:\n",
    "                    ret = max(ret, j - i + 1)\n",
    "        return ret \n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        ret = s = 0\n",
    "        d = {}\n",
    "        for i, x in enumerate(hours):\n",
    "            s += 1 if x > 8 else -1\n",
    "            if s > 0:\n",
    "                ret = i + 1\n",
    "            elif s - 1 in d:\n",
    "                ret = max(ret, i - d[s-1])\n",
    "            if s not in d:\n",
    "                d[s] = i\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        st = [0]\n",
    "        n = len(hours)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            pre[i] = pre[i - 1] + (1 if h > 8 else -1)\n",
    "            if pre[i] < pre[st[-1]]: st.append(i)\n",
    "        ret = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and pre[i] > pre[st[-1]]:\n",
    "                ret = max(ret, i - st.pop())\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        mat = {}\n",
    "        s = 0\n",
    "        preSum = []\n",
    "        for i in range(len(hours)):\n",
    "            if hours[i] > 8: s += 1\n",
    "            else: s += -1\n",
    "            if not s in mat:\n",
    "                mat[s] = i\n",
    "            preSum.append(s)\n",
    "        ans = 0\n",
    "        for i in range(len(preSum)):\n",
    "            if preSum[i] > 0:\n",
    "                ans = max(ans, i + 1)\n",
    "            else:\n",
    "                if preSum[i] - 1 in mat and mat[preSum[i] - 1] < i:\n",
    "                    ans = max(ans, i - mat[preSum[i] - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        nums = [1 if hour > 8 else -1 for hour in hours]\n",
    "        st = [0]\n",
    "        n = len(hours)\n",
    "        pre_sm = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            pre_sm[j] = pre_sm[j-1]+nums[j-1]\n",
    "            if pre_sm[j] < pre_sm[st[-1]]:st.append(j)\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and pre_sm[i] > pre_sm[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())  # [st[-1],i) 可能是最长子数组\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n=len(hours)\n",
    "        eff=[]\n",
    "        for i in range(n):\n",
    "            if hours[i]>8:\n",
    "                eff.append(1)\n",
    "            else:\n",
    "                eff.append(-1)\n",
    "        presum=[0]\n",
    "        for j in range(n):\n",
    "            presum.append(presum[-1]+eff[j])\n",
    "\n",
    "        stack=[]\n",
    "        ans=0\n",
    "\n",
    "        for i,num in enumerate(presum):\n",
    "            if not stack or presum[stack[-1]]>=num:\n",
    "                stack.append(i)\n",
    "\n",
    "        for u in range(n,-1,-1):\n",
    "            if u<ans:\n",
    "                break\n",
    "            while stack and presum[stack[-1]]<presum[u]:\n",
    "                ans=max(ans,u-stack.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        s = [0] * (n + 1)\n",
    "        st = [0]  # s[0]\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            s[j] = s[j - 1] + (1 if h > 8 else -1)  # 求前缀和\n",
    "            if s[j] < s[st[-1]]:  # 感兴趣的j\n",
    "                st.append(j)\n",
    "        ans = 0\n",
    "        for i in range(n, 0, - 1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pre = [0] * (n + 1) \n",
    "        stack = [0]\n",
    "        for j, h in enumerate(hours, 1):\n",
    "            pre[j] = pre[j - 1] + (1 if h > 8 else -1)\n",
    "            if pre[j] < pre[stack[-1]]: stack.append(j)  \n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while stack and pre[i] > pre[stack[-1]]:\n",
    "                ans = max(ans, i - stack.pop()) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n=len(hours)\n",
    "        eff=[]\n",
    "        for i in range(n):\n",
    "            if hours[i]>8:\n",
    "                eff.append(1)\n",
    "            else:\n",
    "                eff.append(-1)\n",
    "        presum=[0]\n",
    "        for j in range(n):\n",
    "            presum.append(presum[-1]+eff[j])\n",
    "\n",
    "        stack=[]\n",
    "        ans=0\n",
    "\n",
    "        for i,num in enumerate(presum):\n",
    "            if not stack or presum[stack[-1]]>=num:\n",
    "                stack.append(i)\n",
    "\n",
    "        for u in range(n,-1,-1):\n",
    "            if u<ans:\n",
    "                break\n",
    "            while stack and presum[stack[-1]]<presum[u]:\n",
    "                ans = max(ans,u-stack.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        stack = [0]\n",
    "        pre = [0]*(n+1)\n",
    "        ans = 0\n",
    "        for i,h in enumerate(hours,1):\n",
    "            if h>8:\n",
    "                pre[i] = pre[i-1]+1\n",
    "            else:\n",
    "                pre[i] = pre[i-1]-1\n",
    "            if pre[i] < pre[stack[-1]]: #降序栈，将有可能成为左端点的加入队列中\n",
    "                stack.append(i)\n",
    "        for i in range(n,0,-1):\n",
    "            while stack and pre[i] > pre[stack[-1]]:#\n",
    "                ans = max(ans,i-stack.pop())\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        preSum = [0]\n",
    "        stack = [0]\n",
    "        for i, hour in enumerate(hours):\n",
    "            preSum.append(preSum[-1] + (1 if hour > 8 else -1))\n",
    "            if preSum[-1] < preSum[stack[-1]]:\n",
    "                stack.append(i+1)\n",
    "\n",
    "        res = 0\n",
    "        # 找(i,j)使 preSum[j] - preSum[i] > 0\n",
    "        # 对 j 而言 只需要找到符合上述条件的、最大的j\n",
    "        # 对 i 而言 在i < i1 < j中，可行的i1必须满足preSum[i1] < preSum[i] \n",
    "        # --> 构造以 i 开始的递减栈\n",
    "        # 栈里记录所有可行 i1 (i < i1 < j)\n",
    "        for j in range(len(preSum) - 1, -1, -1):\n",
    "            while len(stack) != 0 and preSum[j] - preSum[stack[-1]] > 0:\n",
    "                res = max(res, j - stack[-1])\n",
    "                stack.pop()\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        print(preSum)\n",
    "        print(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        \n",
    "        n = len(hours)\n",
    "        prefixSum = [0] * (n+1)\n",
    "        stack = [0]   # monotonic decreasing stack, element: index of prefix sum\n",
    "        for i in range(1, n+1):\n",
    "            prefixSum[i] = prefixSum[i-1] + (1 if hours[i-1] > 8 else -1)    # convert hour to +1 (h>8), -1 (h<=8)\n",
    "            if prefixSum[stack[-1]] > prefixSum[i]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        # 外层循环：从后往前遍历前缀和\n",
    "        for i in range(n, 0, -1):\n",
    "            # 内层循环：从后往前遍历单调栈，满足条件则弹出末尾下标\n",
    "            while stack and prefixSum[i] > prefixSum[stack[-1]]:\n",
    "                ans = max(ans, i - stack.pop())\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        ps = [0] * (n+1)\n",
    "        st = [0]\n",
    "\n",
    "        for i, h in enumerate(hours, 1):\n",
    "            ps[i] = ps[i-1] + int(h > 8) * 2 - 1\n",
    "            if ps[i] < ps[st[-1]]:\n",
    "                st.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            while st and ps[i] > ps[st[-1]]:\n",
    "                ans = max(ans, i - st[-1])\n",
    "                st.pop()\n",
    "        \n",
    "        return ans\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestWPI(self, hours: List[int]) -> int:\r\n",
    "        len_hours = len(hours)\r\n",
    "        hours_dic = {}\r\n",
    "        presum = [0 for _ in range(len_hours + 1)]\r\n",
    "        for i in range(1, len_hours + 1):\r\n",
    "            if hours[i - 1] > 8:\r\n",
    "                presum[i] = presum[i - 1] + 1\r\n",
    "            else:\r\n",
    "                presum[i] = presum[i - 1] - 1\r\n",
    "            hours_dic[presum[i]] = i\r\n",
    "\r\n",
    "        if presum[-1] > 0:\r\n",
    "            return len_hours\r\n",
    "\r\n",
    "        max_len = 0\r\n",
    "        for i in range(len_hours + 1):\r\n",
    "            # right=hours_dic[presum[i]+1]\r\n",
    "            if presum[i] + 1 in hours_dic and hours_dic[presum[i] + 1] > i:\r\n",
    "                max_len = max(max_len, hours_dic[presum[i] + 1] - i)\r\n",
    "        return max_len\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI0(self, hours: List[int]) -> int:\n",
    "        # 不能用滑动窗口，因为不能确定左边界+1的时机\n",
    "        l = 0\n",
    "        hours = [0 if x < 8 else 1 for x in hours ]\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for r, nr in enumerate(hours):\n",
    "            print(r,c)\n",
    "            c[nr] += 1\n",
    "            while l < r and c[1] <= c[0]:\n",
    "                c[l] -= 1\n",
    "                l += 1\n",
    "            if c[1] > c[0]:\n",
    "                ans = max(ans, r-l+1)\n",
    "        return ans\n",
    "\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        hours = [1 if x>8 else -1 for x in hours]\n",
    "        preSum = [0] * (len(hours)+1)\n",
    "        st = [0]\n",
    "        for i, x in enumerate(hours,1):\n",
    "            preSum[i] = preSum[i-1] + x\n",
    "            if preSum[i] < preSum[st[-1]]:\n",
    "                st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(len(preSum)-1,-1,-1):\n",
    "            while st and preSum[st[-1]] < preSum[r]:\n",
    "                ans = max(ans, r-st.pop())\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        hours = [1 if hours[i]>8 else -1 for i in range(n)]\n",
    "        pre = list(accumulate(hours, initial=0))\n",
    "\n",
    "        sta = [0]\n",
    "        for i in range(1, n+1):\n",
    "            if pre[i]<pre[sta[-1]]:\n",
    "                sta.append(i)\n",
    "        \n",
    "        max_len = 0\n",
    "        for i in range(n,0,-1):\n",
    "            while sta and pre[i]>pre[sta[-1]]:\n",
    "                max_len = max(max_len, i - sta.pop())\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        res = 0\n",
    "        prix = [0]\n",
    "        stack = [0]\n",
    "        for i in range(len(hours)):\n",
    "            prix.append(prix[-1] + (1 if hours[i] > 8 else -1))\n",
    "            if prix[stack[-1]] > prix[-1]:\n",
    "                stack.append(i+1)\n",
    "        for i in range(len(prix)-1, 0, -1):\n",
    "            while stack and prix[stack[-1]] < prix[i]:\n",
    "                res = max(res, i - stack.pop())\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n = len(hours)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + 2 * int(hours[i] > 8) - 1\n",
    "        \n",
    "        print(pre)\n",
    "        mp = dict()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            # >0一定有长度\n",
    "            if pre[i] > 0:\n",
    "                ans = max(ans, i)\n",
    "            else:\n",
    "                if pre[i]-1 in mp:\n",
    "                    ans = max(ans, i - mp[pre[i]-1])\n",
    "                if not pre[i] in mp:\n",
    "                    mp[pre[i]] = i\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n=len(hours)\n",
    "        eff=[]\n",
    "        for i in range(n):\n",
    "            if hours[i]>8:\n",
    "                eff.append(1)\n",
    "            else:\n",
    "                eff.append(-1)\n",
    "        presum=[0]\n",
    "        for j in range(n):\n",
    "            presum.append(presum[-1]+eff[j])\n",
    "\n",
    "        stack=[]\n",
    "        ans=0\n",
    "\n",
    "        for i,num in enumerate(presum):\n",
    "            if not stack or presum[stack[-1]]>=num:\n",
    "                stack.append(i)\n",
    "\n",
    "        for u in range(n,-1,-1):\n",
    "            if u<ans:\n",
    "                break\n",
    "            while stack and presum[stack[-1]]<presum[u]:\n",
    "                ans=max(ans,u-stack.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        arr = [1 if h>8 else -1 for h in hours]\n",
    "        presum = [0] + list(accumulate(arr))\n",
    "        res = 0\n",
    "        neg_map = {}\n",
    "        for i,s in enumerate(presum):\n",
    "            if s>0:\n",
    "                res = max(res,i)\n",
    "            else:\n",
    "                if s-1 in neg_map:\n",
    "                    res = max(res,i-neg_map[s-1])\n",
    "                if s not in neg_map:\n",
    "                    neg_map[s] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        map_d = defaultdict(int)\n",
    "        l = len(hours)\n",
    "        pre_sum = [0 for i in range(l+1)]\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            if hours[i]>8:\n",
    "                hours[i]=1\n",
    "            else:\n",
    "                hours[i]=-1\n",
    "        for i in range(1,l+1):\n",
    "            pre_sum[i] = pre_sum[i-1]+hours[i-1]\n",
    "            if(pre_sum[i] not in map_d):\n",
    "                map_d[pre_sum[i]]= i\n",
    "        for i in range(0,l+1):\n",
    "            if pre_sum[i]>0:\n",
    "                res = max(res,i)\n",
    "            elif pre_sum[i]<=0:\n",
    "                target = pre_sum[i]-1\n",
    "                if target in map_d:\n",
    "                    res = max(res,i-map_d[target])\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n=len(hours)\n",
    "\n",
    "        for i in range(n):\n",
    "            hours[i]=1 if hours[i]>8 else -1\n",
    "\n",
    "        dicc=defaultdict(int)\n",
    "\n",
    "        summ=[0]\n",
    "        for i in hours:\n",
    "            summ.append(summ[-1]+i)\n",
    "        ans=0\n",
    "        for i in range(len(summ)):\n",
    "            if summ[i]>0:\n",
    "                ans=max(ans,i)\n",
    "            else:\n",
    "                target=summ[i]-1\n",
    "                if target in dicc:\n",
    "                    ans=max(ans,i-dicc[target])            \n",
    "\n",
    "            if summ[i] not in dicc:\n",
    "                dicc[summ[i]]=i\n",
    "\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        l = 0\n",
    "        res = 0\n",
    "        window = 0\n",
    "\n",
    "        s = []\n",
    "        for val in hours:\n",
    "            if val > 8:\n",
    "                s.append(1)\n",
    "            else:\n",
    "                s.append(-1)\n",
    "        \n",
    "        prefixSum = [0]\n",
    "        for val in s:\n",
    "            tmp = val + prefixSum[-1]\n",
    "            prefixSum.append(tmp)\n",
    "        \n",
    "    \n",
    "        def helper(nums):\n",
    "            n = len(nums)\n",
    "            st = [0]  # s[0]\n",
    "            for i, h in enumerate(nums):\n",
    "                if h < nums[st[-1]]: \n",
    "                    st.append(i)\n",
    "            ans = 0\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                while st and nums[i] > nums[st[-1]]:\n",
    "                    ans = max(ans, i - st.pop())  \n",
    "            return ans\n",
    "        \n",
    "        res = helper(prefixSum)\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        h = [1 if i > 8 else -1 for i in hours]\n",
    "        sh = [0] * len(hours)\n",
    "        s = 0\n",
    "        for i in range(len(h)):\n",
    "            s += h[i]\n",
    "            sh[i] = s\n",
    "        seen = {}\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(sh)):\n",
    "            if sh[i] > 0:\n",
    "                res = max(res, i + 1)\n",
    "            else:\n",
    "                if sh[i] - 1 in seen:\n",
    "                    res = max(res, i - seen[sh[i] - 1])\n",
    "                if sh[i] not in seen:\n",
    "                    seen[sh[i]] = i\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        nums = [1 if h > 8 else -1 for h in hours]\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "\n",
    "        st = [0]\n",
    "        for i, x in enumerate(s):\n",
    "            if st and x < s[st[-1]]:\n",
    "                st.append(i)\n",
    "\n",
    "        # print(st)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            while st and s[i] > s[st[-1]]:\n",
    "                ans = max(ans, i - st.pop())\n",
    "            else:\n",
    "                if st == []:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        n=len(hours)\n",
    "        eff=[]\n",
    "        for i in range(n):\n",
    "            if hours[i]>8:\n",
    "                eff.append(1)\n",
    "            else:\n",
    "                eff.append(-1)\n",
    "        presum=[0]\n",
    "        for j in range(n):\n",
    "            presum.append(presum[-1]+eff[j])\n",
    "\n",
    "        stack=[]\n",
    "        ans=0\n",
    "\n",
    "        for i,num in enumerate(presum):\n",
    "            if not stack or presum[stack[-1]]>=num:\n",
    "                stack.append(i)\n",
    "\n",
    "        for u in range(n,-1,-1):\n",
    "            if u<ans:\n",
    "                break\n",
    "            while stack and presum[stack[-1]]<presum[u]:\n",
    "                ans = max(ans,u-stack.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWPI(self, hours: List[int]) -> int:\n",
    "        h = [1 if i > 8 else -1 for i in hours]\n",
    "        sh = [0] * len(hours)\n",
    "        s = 0\n",
    "        for i in range(len(h)):\n",
    "            s += h[i]\n",
    "            sh[i] = s\n",
    "        seen = {}\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(sh)):\n",
    "            if sh[i] > 0:\n",
    "                res = max(res, i + 1)\n",
    "            else:\n",
    "                if sh[i] - 1 in seen:\n",
    "                    res = max(res, i - seen[sh[i] - 1])\n",
    "                if sh[i] not in seen:\n",
    "                    seen[sh[i]] = i\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
